package leetcode.剑指offer.后40;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/2 17:40
 * @description :
 */
public class 剑指_56_1_数组中数字出现的次数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.singleNumbers(new int[]{4,1,4,6})));

    }

    class Solution {
        public int[] singleNumbers(int[] nums) {
            //对所有数字进行异或得到a ^ b
            int ret = 0;
            for (int num : nums) {
                ret ^= num;
            }
            //任取不为1的一位（不同为1）
            int div = 1;
            while ((div & ret) == 0) {
                div <<= 1;
            }
            //对原来的数组进行分组
            int a = 0, b = 0;
            for (int num : nums) {
                if ((num & div) == 0) {
                    a ^= num;
                } else
                    b ^= num;
            }
            return new int[]{a, b};
        }
    }

}
